package com.sfx.算法专题.链表.链表相加;

import java.util.Stack;

/**
 * Created with IntelliJ IDEA.
 * Description:
 * User: sfx
 * Date: 2023-08-03
 * Time: 22:53
 */
public class Code_2_addTwoNumbers2 {
    static class ListNode {
        int val;
        ListNode next;

        ListNode(int x) {
            val = x;
            next = null;
        }
    }

    class Solution {
        public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
            Stack<ListNode> s1 = new Stack<>();
            Stack<ListNode> s2 = new Stack<>();
            while(l1!=null) {
                s1.push(l1);
                l1 = l1.next;
            }
            while(l2!=null) {
                s2.push(l2);
                l2 = l2.next;
            }
            int carry = 0;
            int sum = 0;
            ListNode dummy = new ListNode(-1);
            ListNode tmp = dummy;
            while(!s1.isEmpty() || !s2.isEmpty()) {
                int val1 = s1.isEmpty() ? 0 : s1.pop().val;
                int val2 = s2.isEmpty() ? 0 : s2.pop().val;
                sum = val1 + val2;
                ListNode node = new ListNode((sum+carry)%10);
                carry = (sum+carry) / 10;
                node.next = tmp.next;
                tmp.next = node;
            }
            if(carry>0) {
                ListNode node = new ListNode(carry);
                node.next = tmp.next;
                tmp.next = node;
            }
            return dummy.next;
        }
    }
}